/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 * Date:    May 2011
 */

#ifndef __CPU_EDGE_TAGE_EXIT_HH__
#define __CPU_EDGE_TAGE_EXIT_HH__

#include <vector>
#include <deque>

#include "base/statistics.hh"
#include "cpu/edge/pred/base_exit_predictor.hh"
#include "cpu/edge/sat_counter.hh"

/**
 * A TAGE predictor for branch exit of hyperblocks.
 * */
template<class Impl>
class TAGEExitP : public BaseExitPredictor<Impl>
{
  public:
    typedef TheISA::BlockID BlockID;
    typedef TheISA::ExitID ExitID;
    typedef std::deque<Addr> PathHistory;

    enum GlobalIndexMode {
        Address,
        AddressAndPath,
        AddressAndCPath,
        AddressAndHist,
        InvalidGlobalIndexMode
    };

    enum PredictionMode {
        GlobalOnly,
        IncludeLocal, // The last table will be indexed by local history.
        InvalidPredictionMode
    };

    enum TableSizeMode {
        Equal,
        HistPower,
        InvalidTableSizeMode
    };

    /** The constructor. */
    TAGEExitP(DerivEdgeCPUParams *params);

    /** The destructor. */
    ~TAGEExitP();

    void reset();	
    /**
     * Looks up the given block address in the branch predictor and returns
     * an exit ID of the block.  Also creates a
     * BPHistory object to store any state it will need on squash/update.
     */
    TheISA::ExitID lookup(BlockID block_id, BlockID oldest_block_id, 
        Addr &block_addr, int addr_space_ID, ThreadID tid);   

    /**
     * Updates the branch predictor with the actual result of a branch.
     * Return the prediction of before.
     */
    TheISA::ExitID update(BlockID block_id, Addr &block_addr, int addr_space_id,
                              ExitID actual_exit_id,ThreadID tid);

    /**
     * Restores the global branch history on a squash.
     */
    void squash(BlockID block_id, Addr block_pc, ExitID exit_id,
            ThreadID tid);

    /**
     * Restores the global branch history on a squash.
     */
    void squash(BlockID block_id, ThreadID tid);

    uint64_t lookupGetIndex(Addr &block_PC, ThreadID tid);

    uint64_t updateGetIndex(BlockID block_id, Addr &block_PC, ThreadID tid);

    uint64_t getPathHistory(ThreadID tid);

    uint64_t getPathHistory(BlockID block_id, ThreadID tid);

    uint64_t getGlobalHistory(ThreadID tid) { return globalHistory[tid]; }

    uint64_t getGlobalHistory(BlockID block_id, ThreadID tid);

    const std::string &name() const { return _name; }

    void regStats();

    int getCounterBits() { return taggedCtrBits; }

  private:

    const std::string _name;

    GlobalIndexMode globalIndexMode;    

    PredictionMode predictionMode;

    /** Table entry for the default predictor, which is a
     * hysteresis-based table indexed by block address. */
    struct DefaultTableEntry {
        DefaultTableEntry() : exitID(0)
        { counter.reset(); }

	~DefaultTableEntry()
	{}

        /** The prediction. */
	ExitID exitID;

        /** The counter. */
        SatCounter counter;
    };

    /** Table entry for tagged predictors. */
    struct TaggedTableEntry {
        TaggedTableEntry() :
            exitID(0),
            tag(ULL(-1))
        {
            counter.reset();
            useful.reset();
        }

        ~TaggedTableEntry()
        {}

        /** The prediction. */
        ExitID exitID;

        /** The tag. */
        uint64_t tag;

        /** The counter. */
        SatCounter counter;

        /** The useful counter. */
        SatCounter useful;
    };

    typedef std::vector<DefaultTableEntry> DefaultTable;
    typedef std::vector<TaggedTableEntry> TaggedTable;

    struct LFFEntry {
        uint64_t index;
	uint64_t history;
    };

    void initVars();

    inline uint64_t calcLocHistIdx(Addr &block_addr, int addr_space_ID);

    inline uint64_t calcLocPredIdx(Addr &block_addr, uint64_t history);

    inline uint64_t calcGloPredIdx(Addr &block_addr, uint64_t history,
            uint64_t path_hist, int idx);

    void updatePathHistory(PathHistory &path_history, Addr new_pc);

    /** Mask to get the proper index bits into the predictor. */
    uint64_t localPredictorMask;

    /** Array of local history table entries. */
    std::vector<uint64_t> localHistoryTable;

    /** Array of local future file. */
    std::vector<LFFEntry> localFutureFile;
	
    /** Size of the local history table. */
    uint64_t localHistoryTableSize;

    /** Mask of the local history table. */
    uint64_t localHistoryTableMask;

    /** Number of bits for each entry of the local history table.
     *  @todo Doesn't this come from the size of the local predictor?
     */
    uint64_t localHistoryBits;

    /** Mask to get the proper local history. */
    uint64_t localHistoryMask;

    /** Array of counters that make up the default predictor. */
    DefaultTable defaultTable;

    /** Array of counters that make up the tagged predictors. */
    std::vector<TaggedTable*> taggedTables;

    /** 
     * Size of the tagged tables.
     * */
    std::vector<uint64_t> taggedTableSize;

    /**
     * If all the tagged table are allocated with the same size, this
     * is it.
     * */
    uint64_t fixedTableSize;

    /** The mode of the tagged table size. If it is 'equal', all the
     * tagged tables are allocated with the same size by the variable
     * fixedTableSize; otherwise, each tagged table is allocated with
     * the size that is the 2's power of its history length. */
    TableSizeMode taggedTableSizeMode;

    /** Size of the default table. */
    uint64_t defaultTableSize;

    /** Mask of the tagged table. */
    std::vector<uint64_t> taggedTableMask;

    /** Mask of the default table. */
    uint64_t defaultTableMask;

    /** 
     * Checkpoint entry for each speculative block.
     * @TODO Add local history to this entry.
     * */
    struct CheckpointEntry {
        CheckpointEntry () 
            : blockID(0),
            globalHistory(0),
            providerID(-1),
            alterID(-1),
            providerPrediction(TheISA::MaxExitsInBlock),
            alterPrediction(TheISA::MaxExitsInBlock)
        {
        }

        void reset()
        {
            blockID = 0;
            globalHistory = 0;
            providerID = -1;
            alterID = -1;
            providerPrediction = TheISA::MaxExitsInBlock;
            alterPrediction = TheISA::MaxExitsInBlock;

            for (int i = 0; i < pathHistory.size(); ++i) {
                pathHistory[i] = 0;
            }
        }

        BlockID blockID;
        uint64_t globalHistory;
        PathHistory pathHistory;
        int providerID;
        int alterID;
        ExitID providerPrediction;
        ExitID alterPrediction;
    };

    /** Speculative checkpoints. */
    CheckpointEntry checkpointEntries[Impl::MaxInFlightBlockNum];

    /** Global history register. */
    uint64_t globalHistory[Impl::MaxThreads];

    /** Path histories of all threads, speculatively updated. */
    PathHistory pathHistoryTable[Impl::MaxThreads];

    /** Global history file. */
    //std::vector<uint64_t> globalHistoryFile;

    /** Path histories of all in-flight blocks. */
    //PathHistory pathHistoryFile[Impl::MaxInFlightBlockNum];

    /** Number of bits for histories that form a geometric series. */
    std::vector<uint64_t> globalHistoryBits;

    /** Masks to get the proper global history. */
    std::vector<uint64_t> globalHistoryMasks;

    /** Number of bits for tagged tables' counter. */
    int taggedCtrBits;

    /** Number of bits for default tables' counter. */
    uint64_t defaultCtrBits;

    /** Number of bits for tagged tables' useful counter. */
    uint64_t taggedUsefulCtrBits;

    /** Number of bits for tags in tagged tables. */
    uint64_t tagBits;

    /** Mask of tags in tagged tables. */
    uint64_t tagMask;

    /** Number of tagged tables. */
    uint64_t numTaggedTables;

    // This is the geometric series formula:
    // li = alpha^(i-1) * l1
    
    /** Factor of the geometric series. */
    double alpha;

    /** The shortest global history length. */
    uint64_t l1;

    /** Number of bits to shift the instruction over to get rid of the word
     *  offset.
     */
    uint64_t blockShiftAmt;

    /** Threshold for the counter value; larger or equal to the threshold,
     * prediction will not be updated, otherwise the prediction is
     * updated.
     */
    uint64_t defaultThreshold;
    uint64_t taggedThreshold;

    /** Exit id bits. */
    int exitIdBits;

    /** Exit id mask. */
    uint64_t exitIdMask;

    /** Stats for recording the provider. */
    Stats::Distribution correctProvider;

    /** Stats for recording the incorrect provider. */
    Stats::Distribution incorrectProvider;
};

#endif // __CPU_EDGE_TAGE_EXIT_HH__
